package org.example.myleet.p994;

public class Solution {

    private static final int BLANK = 0;
    private static final int FRESH = 1;
    private static final int ROTTEN = 2;

    private static int[] DR = {-1, 0, 1, 0};
    private static int[] DC = {0, 1, 0, -1};

    public int orangesRotting(int[][] grid) {
        int nr = grid.length, nc = grid[0].length, time = -1, size = 0, freshCount = 0;
        int[][] pointQueue = new int[nr * nc][2];
        int[][] tempQueue = new int[nr * nc][2];
        boolean[][] visited = new boolean[nr][nc];
        for (int i = 0; i < nr; ++i) {
            for (int j = 0; j < nc; ++j) {
                if (grid[i][j] == FRESH) {
                    ++freshCount;
                } else if (grid[i][j] == ROTTEN) {
                    pointQueue[size++] = new int[]{i, j};
                }
            }
        }
        if (freshCount == 0) {
            //一开始就没有新鲜橘子，符合题意，不消耗时间
            return 0;
        }
        if (size == 0) {
            //存在新鲜橘子，但没有腐烂的橘子，因此总剩下新鲜橘子，因此不可能全部腐烂
            return -1;
        }
        while (size > 0) {
            int len = size;
            size = 0;
            for (int i = 0; i < len; ++i) {
                int[] p = pointQueue[i];
                if (grid[p[0]][p[1]] == FRESH) {
                    //腐烂一个橘子，并减少一个新鲜橘子数
                    grid[p[0]][p[1]] = ROTTEN;
                    --freshCount;
                }
                for (int k = 0; k < 4; ++k) {
                    //BFS，向4个方向延伸寻找新鲜橘子，用于下一回合腐烂
                    int r = p[0] + DR[k];
                    int c = p[1] + DC[k];
                    if (0 <= r && r < nr && 0 <= c && c < nc && grid[r][c] == FRESH && !visited[r][c]) {
                        tempQueue[size++] = new int[]{r, c};
                        visited[r][c] = true;
                    }
                }
            }
            if (size >= 0) {
                System.arraycopy(tempQueue, 0, pointQueue, 0, size);
            }
            ++time;
        }
        if (freshCount > 0) {
            return -1;
        }
        return time;
    }
}
